package LeetCode;

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class LeetCodeMain20 {
    public int totalMoney(int n) {
        int count1=n/7;
        int sum=28*count1;
        int count2=n%7;
        int flag=0;
        for (int i = 1; i < count1; i++) {
            flag+=7;
            sum+=flag;
        }
        flag=count1+1;
        for (int i = 0; i < count2; i++) {
            sum+=flag;
            flag++;
        }
        return sum;
    }
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int sum=0;
        int count=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            if (map.containsKey(sum-k)){
                count+=map.get(sum-k);

            }map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (prerequisites[i][0]==prerequisites[i][1]){
                return false;
            }
            if (map.containsKey(prerequisites[i][1])){
                if (map.get(prerequisites[i][1])==prerequisites[i][0]){
                    return false;
                }
            }else {
                map.put(prerequisites[i][0],prerequisites[i][1]);
            }
        }
        return true;
    }
    public int count(int n){
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        if (n<=0){
            return 0;
        }
        return count(n-1)+count(n-2);
    }
    public int climbStairs(int n) {
        if (n==1){
            return 1;
        }
        int n1=1;
        int n2=2;
        int n3=0;
        for (int i = 3; i <= n; i++) {
            n3=n1+n2;
            n1=n2;
            n2=n3;
        }
        return n2;
    }
    public int maxSubArray(int[] nums) {
        int sum=0;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            if (sum>max){
                max=sum;
            }
            if (sum<0){
                sum=0;
            }
        }
        return max;
    }
    List<TreeNode> list=new ArrayList<>();
    public void prev(TreeNode root){
        if (root==null){
            return;
        }
        list.add(root);
        prev(root.left);
        prev(root.right);
    }
    public void flatten(TreeNode root) {
        if (root==null){
            return;
        }
        prev(root);
        root=list.get(0);
        TreeNode node=root;
        for (int i = 1; i < list.size(); i++) {
            node.left=null;
            node.right=list.get(i);
            node=node.right;
        }
    }
}
